The problem can be found at the following link: Question Link
To insert a node in a Binary Search Tree (BST), we start at the root and traverse the tree while comparing the data to be inserted with the data in the current node.
- If the data is less than the current node's data, we move to the left subtree.
- If it's greater, we move to the right subtree.
- We repeat this process until we find an empty spot to insert the new node.
Here are the steps of my approach:
- If the BST is empty (root is null), create a new node with the given data and make it the root of the tree.
- If the data to be inserted is greater than the current node's data, move to the right subtree.
- If the right child of the current node is null, create a new node with the data and make it the right child
- otherwise, repeat the process recursively with the right child.
- If the data to be inserted is less than the current node's data, move to the left subtree.
- If the left child of the current node is null, create a new node with the data and make it the left child.
- otherwise, repeat the process recursively with the left child.
-
Time Complexity: In the worst case, when the tree is highly unbalanced and resembles a linked list, the time complexity for insertion is
O(n)
, wheren
is the number of nodes in the tree. However, in a well-balanced BST, the time complexity isO(log n)
on average. -
Auxiliary Space Complexity: The space complexity is
O(h)
, whereh
is the height of the tree. In the worst case (highly unbalanced tree), it can beO(n)
, and in the best case (well-balanced tree), it'sO(log n)
.
class Solution {
public:
Node* insert(Node* node, int data) {
if (!node)
return new Node(data);
if (data > node->data){
if (!node->right)
node->right = new Node(data);
else
insert(node->right, data);
} else if (data < node->data){
if (!node->left)
node->left = new Node(data);
else
insert(node->left, data);
}
return node;
}
};
For discussions, questions, or doubts related to this solution, please visit our discussion section. We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the getlost01/gfg-potd repository.